/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"
#include <iostream>

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    	rootPid = -1;
	treeHeight = 0;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
	// Open a file on disk
	const string index = indexname + ".idx";
	if ( pf.open(index, mode) != 0 )
	{
		cout << "Error: Cannot create an index file" << endl;
		exit(1);
	}

    	return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	pf.close();
    	return 0;
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
	BTLeafNode leaf;
	BTNonLeafNode nonLeaf;
	int status;

	// First get the key count of the node to see 
	// if we can insert or not
	PageFile newPF;
	leaf.read(0, newPF);		// All pid use 0 now, assume testing for 1 lvl tree
	int keyCount;
	keyCount = leaf.getKeyCount();

	// If node is not full, just insert
	// else, we need to split
	if (keyCount < 85)
	{
		leaf.insert(key, rid);
		if ( rootPid == -1)
		{
			treeHeight ++;
			rootPid = 0;
		}
		leaf.write(0, newPF);
		return 0;
	}
	else
	{
		// Load a sibling instance, sibling should be empty
		BTLeafNode sibling;
		PageFile sibPF;
		sibling.read(1, sibPF);
		int sibKey;

		// Insert and split
		leaf.insertAndSplit(key, rid, sibling, sibKey);
		leaf.setNextNodePtr(1);

		// Update the memory buffer and write back to page (disk)
		leaf.write(0, newPF);
		sibling.write(1, sibPF);

		// sibKey gets return, this is the key that we want to put
		// in the non-leaf node.
		// We check the treeHeight, if there's only leaf node, initialize root
		if ( treeHeight == 1 )
		{
			/*
			 * Here I'm assuming that the pid of the non-leaf node starts at 0
			 * and increment by 1
			 * --------------------------
			 * | 0 | key | 1 | key | 2 | .........		
			 * --------------------------
			 * Later on, I'll have to maintain a counter for all the pageId in 
			 * non-leaf node. Perhaps a private member in index and store in disk
			 */

			// Load a non-leaf node instance
			BTNonLeafNode root;
			PageFile rootPF;
			root.read(2, rootPF);
			root.initializeRoot(0, sibKey, 1);
			
			// Set the root pid
			rootPid = 2;
			treeHeight = 2;
			root.write(2, rootPF);
			return 0
		}
		else
		{
			// Search from root where pid = 2
			BTNonLeafNode searchNode;
			PageFile searchPF;
			PageId target = 2;
				
			// Load the searchNode (root) instance and get its key count
			searchNode.read(target, searchPF);
			int keyCount = searchNode.getkeyCount();

			if ( keyCount < 127)
			{
				searchNode.insert(sibKey, 3);
				searchNode.write(3, searchPF);
				return 0;
			}
			else
			{
				cout << "3 level B+ tree is not implemented " << endl;
				exit(1);
			}
		}
	}
	

	return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
	if ( treeHeight == 0)
	{
		cout << "Error: The index is empty, cannot find any key" << endl;
		exit(1);
	}

	int height = 1;
	int searchPid = rootPid;

	// Start from the root node and go one level down each time
	// until we find a leaf node
	while ( height < treeHeight)
	{
		BTNonLeafNode nonLeaf;
		nonLeaf.read(searchPid, pf);
	
		int nextPid;
		if ( nonLeaf.locateChildPtr(searchKey, nextPid) == 0)
		{
			height ++;
			searchPid = nextPid;
		}
	}

	// We found the leaf node
	BTLeafNode leaf;
	int entry;
	leaf.read(searchPid, pf);
	int status = leaf.locate(searchKey, entry);

	// Return 0 if we can locate the serachKey
	// and return -1 if not
	if ( status == 0)
	{
		cursor.eid = entry;
		cursor.pid = searchPid;
		return 0;
	}
	else
		return -1;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	// Create a leaf node
	BTLeafNode leaf;

	leaf.read(cursor.pid, pf);
	leaf.readEntry(cursor.eid, key, rid);
	
	return 0;
}
